package com.example.leetcode.prcatice;

/**
 * 给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
 *
 * 给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/possible-bipartition
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test886 {

    int[] p;// 并查集数组
    public boolean possibleBipartition(int n, int[][] dislikes) {
        /* 将并查集分为两类
        - p[1，...i - 1, i, i + 1…N]代表数字属于第一类:p[i]维护的是和编号i非敌人的编号的父节点，
        - p[N + 1…...i - 1 + N, i + N, i + 1 + N…2*N]代表数字属于第二类，p[i + N]维护的是和编号i为敌人的编号的父节点。
        */
        p = new int[2 * n + 1];
        // 初始化（1，2，... , n）编号并查集
        for (int i = 1; i < 2 * n + 1; i ++) {
            p[i] = i;
        }
        for (int[] d : dislikes) {
            int a = d[0], b = d[1];// 相互不喜欢的俩人
            if (find(a) == find(b)) {
                return false;
            } else {// 敌人的敌人就是朋友
                p[find(a)] = find(b + n);
                p[find(b)] = find(a +n);
            }
        }
        return true;
    }
    public int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}
